﻿using System;
using Lists = Algoritmia.DataStructures.Lists;
using System.Collections.Generic;
using System.Linq;

namespace Algoritmia.Problems.Sorting
{
    public class CountingSorter : ISorter<int>
    {
        #region ISorter<int> Members

        public IEnumerable<int> Sorted(Lists.IList<int> list, Comparison<int> comparison = null)
        {
            if (list.Count == 0) 
                yield break;
            int[] b = new int[list.Count];
            int maximum = list.Max() + 1;
            int[] counts = new int[maximum];

            foreach(int value in list)
            {
                counts[value]++;
            }

            for(var i = 1; i < maximum;i++)
            {
                counts[i] += counts[i - 1];
            }

            for(var j = list.Count - 1; j >= 0; j--)
            {
                b[counts[list[j]] - 1] = list[j];
                counts[list[j]]--;
            }
            foreach (int v in b)
                yield return v;
        }

        #endregion
    }
}
